//I figured out what was wrong. It was a logical error. I had the pointer pointing 
//to the last node, but when it was sorted, it was moved around, so it was never
//starting near the end. to correct this i realized that the only time the last node
//entered would be moved, was if it was the highest value. so i inserted the line
//lastNode = highestVal->previous, where highestVal is the address of the highest value
//in the list, under the conditions where highestVal->next == NULL. i 
//should spend more time tracing my code :)


#include <iostream>
#include "list.h"

using namespace std;

void Head::createList(int num)
{
	List* nodePtr, *previousPtr;
	nodePtr = previousPtr = head;

	if(head == NULL)
	{
		head = new List(num);
	}
	else
	{
		nodePtr = head;

		//traverses the list until nodePtr leaves the list.
		//prevPtr perserves the position of the last node.

		while(nodePtr)
		{
			previousPtr = nodePtr;
			nodePtr = nodePtr->next;
		}

		//previousPtr->next will now point to the newly
		//created node, and receives the values num and the address
		//of previousPtr. previousPtr is passed as an argument to ensure
		//the doubly linked list is linked together in reverse order.
		//this is essential to reordering the list later on in the
		//selection sort algorithm.

		lastNode = previousPtr->next = new List(num, previousPtr);		
	}
}

void Head::quickSort()
{
	List* nodePtr, *highestVal, *start;
	nodePtr = highestVal = head;

	highestVal = head;

	start = head;

	while(start)
	{
		nodePtr = start;

		//while loop cycles through the entire list each time to locate
		//the node that contains the highest value. highest then stores
		//this value and highestVal is assigned to point to this node.

		while(nodePtr)
		{
			if(nodePtr->value >= highestVal->value)
			{
				highestVal = nodePtr;
			}

			nodePtr = nodePtr->next;
		}

		//this statement determines if the highestVal is in the same location as
		//the start pointer. if it is, then the start pointer is moved to the next
		//spot in the list. this is the ONLY condition that causes the start pointer
		//to move down the list. 

		if(highestVal->value == start->value)
		{
			start = start->next;
		}

		//this elif statement checks to see if the highest value is being moved from
		//the end of the list to the front of the list, if it is, then the highestVal->next == NULL
		//needs to be taken into account and worked around.

		else if(head->value < highestVal->value && start == head && highestVal->next == NULL)
		{
			head = highestVal;
			lastNode = highestVal->previous;
			highestVal->previous->next = highestVal->next;
			highestVal->next = start;
			start->previous = highestVal;
			highestVal->previous = NULL;
		}

		//this if statement checks the same conditions as the previous statement
		//with the exception of checking to see if highestVal->next == NULL. this 
		//statement is needed if the value is being moved from anywhere in the list, except
		//from the last position, to the first. this is needed because of the statement
		//highestVal->next->previous = highestVal->previous. this is to reverse link the 
		//node after highestVal with the node before highestVal. if this statement is used in 
		//the previous condition, then it will result in a segmentation fault.

		else if(head->value < highestVal->value && start == head)
		{
			head = highestVal;
			highestVal->previous->next = highestVal->next;
			highestVal->next->previous = highestVal->previous;
			highestVal->next = start;
			highestVal->previous = NULL;
			start->previous = highestVal;
		}

		//this if statement checks the condition to see if the value is being moved
		//from the last position to any other position on the list, with the exception
		//of being moved to the first. 

		else if(head != start && start->value < highestVal->value && highestVal->next == NULL)
		{
			lastNode = highestVal->previous; //stores the lastNode in the list
			start->previous->next = highestVal;
			highestVal->previous->next = highestVal->next;
			highestVal->previous = start->previous;
			highestVal->next = start;
			start->previous = highestVal;
		}

		//this is the default condition, and is used appropriately when all the 
		//previous conditions fail. 

		else 
		{
			start->previous->next = highestVal;
			highestVal->previous->next = highestVal->next;
			highestVal->next->previous = highestVal->previous;
			highestVal->next = start;
			highestVal->previous = start->previous;
			start->previous = highestVal;
		}

		highestVal = start; //resets the position of highestVal to whatever start is pointing to.
	}
}

void Head::printList()
{
	List* nodePtr;
	nodePtr = head;

	while(nodePtr)
	{
		cout << nodePtr->value << endl;
		nodePtr = nodePtr->next;
	}
}

void Head::reversePrint()
{
	List* nodePtr;
	nodePtr = lastNode;

	while(nodePtr)
	{
		cout << nodePtr->value << endl;
		nodePtr = nodePtr->previous;
	}
}

Head::~Head()
{
	List* nodePtr, *prevPtr;
	nodePtr = prevPtr = head;

	while(nodePtr)
	{
		prevPtr = nodePtr;
		nodePtr = nodePtr->next;
		delete prevPtr;
	}

	cout << "\n\nList Destroyed!\n\n";
}
